import java.util.Arrays;

/**
 * @ClassName Code03_BSExist
 * @Description: TODO
 * @Author: JCC
 * @CreateTime: 2023/11/28 22:12
 */
public class Code04_BSExist {
    public static boolean exist(int[] testArray, int num) {
        if (testArray == null || testArray.length == 0) {
            return false;
        }
        int left = 0;
        int right = testArray.length - 1;
        /*while (left <= right) { // 至少有两个数
            int mid = left + ((right - left) >> 1);
            if (testArray[mid] == num) {
                return true;
            } else if (testArray[mid] > num) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return false;*/

        while (left < right) { // 至少有两个数
            int mid = left + ((right - left) >> 1);
            if (testArray[mid] == num) {
                return true;
            } else if (testArray[mid] > num) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        // 这里不能用right因为当要找的数比最小的数都要小的时候下标越界，
        // 因为当只有left和right之间只有两个数的时候mid都是在left的位置，起到保护left的作用
        // 即使是要找的数比最大值都大的时候也不会是left越界
        return testArray[left] == num;
    }

    // 测试函数
    public static boolean test(int[] testArray, int num) {
        if (testArray == null || testArray.length == 0) {
            return false;
        }
        for (int cur : testArray) {
            if (cur == num) {
                return true;
            }
        }
        return false;
    }

    // 生成随机数组函数
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] randArray = new int[(int) (Math.random() * (maxSize + 1))];
        int len = randArray.length;
        for (int i = 0; i < len; i++) {
            randArray[i] = (int) (Math.random() * (maxValue + 1) - (int) Math.random() * maxValue);
        }
        return randArray;
    }

    public static void main(String[] args) {
        int testTimes = 1000000;
        int maxSize = 10;
        int maxValue = 1000;
        for (int i = 0; i < testTimes; i++) {
            int[] randArray = generateRandomArray(maxSize,maxValue);
            Arrays.sort(randArray);
            int num = (int) (Math.random() * (maxValue + 1) - Math.random() * maxValue);
            if (exist(randArray,num) != test(randArray,num)) {
                System.out.println(Arrays.toString(randArray));
                System.out.println(num);
                System.out.println("fucking fucked！！！");
                return;
            }
        }
        System.out.println("nice！！！");
    }
}
